package com.coder.algorithm.leetcode

/**
 * [138. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)
 *
 * @author yuhus
 * @date: 2022/4/8
 */
object l_0138 {
    class Node(var `val`: Int) {
        var next: Node? = null
        var random: Node? = null
    }

    /**
     * 长度为 n 的链表，0 <= n <= 1000
     */
    fun copyRandomList(node: Node?): Node? {
        if (node == null) {
            return null
        }
        var cur = node
        // 复制节点，并链接到原节点后面
        while (cur != null) {
            val copy = Node(cur.`val`)
            copy.next = cur.next
            cur.next = copy

            cur = copy.next
        }
        // 设置 copy 节点的 random
        cur = node
        while (cur != null) {
            cur.next?.random = cur.random?.next
            cur = cur.next?.next
        }
        // 将链表拆分
        val copyHead = node.next
        cur = node
        while (cur != null) {
            val copy = cur.next
            cur.next = cur.next?.next
            copy?.next = copy?.next?.next

            cur = cur.next
        }
        return copyHead
    }
}